import java.util.ArrayList;
import java.util.Collections;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-05-22
 * Time: 20:56
 */
class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val){
        this.val=val;
    }
}
public class Solution3 {
    public ListNode sortInList (ListNode head) {
        //方法三，转化为数组排序
        ArrayList<Integer> arrayList=new ArrayList<>();
        ListNode cur=head;
        while (cur!=null){
            arrayList.add(cur.val);
            cur=cur.next;
        }
        /*Collections.sort(arrayList);
        ListNode res=new ListNode(-1);
        cur=res;
        for(Integer node:arrayList){
            cur.next=new ListNode(node);
            cur=cur.next;
        }
        return res.next;*/
        //也可以不够造新的链表，直接在原来的链表上修改节点的值
        Collections.sort(arrayList);
        cur=head;
        for (Integer integer : arrayList) {
            cur.val = integer;
            cur = cur.next;
        }
        return head;
    }
}
